﻿#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

// 节点对应的结构体
typedef struct Node
{
    int num;            // 每个节点中存储的数据，可以有多个
    struct Node* pNext; // 用于保存下一个节点(结构体)的指针
}NODE;

//初始化一个空的带头节点的循环链表
NODE *initList()
{
    NODE *head = malloc(sizeof(NODE));
    if(head != NULL)
    {
        head->pNext = head;
    }
    return head;
}

/* 
* 函数功能：  创建一个新节点
* int n：     当前节点的数据
* 返回类型：  成功:返回当前节点的首地址, 失败:NULL
*/
NODE* createNode(int n)
{
    // 创建新节点
    NODE* pNew = (NODE*)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("createNode %d fail: %s!\n", n, strerror(errno));
        return NULL;
    }

    // 初始化新节点中的成员变量
    pNew->num = n;
    pNew->pNext =pNew;

    // 返回当前节点的首地址
    return pNew;
}

/*
* 函数功能：  删除整个链表(从前向后删除)
* NODE* head：链表首地址
* 返回类型：  无
*/
void distroyList(NODE* head)
{
    for(NODE* p = head->pNext; p != head; p = p->pNext)
    {
        head->pNext = p->pNext;
        free(p);
        p = head->pNext;
    }
    free(head);
}

/*
* 函数功能：  输出整个链表
* NODE* head：链表首地址
* 返回类型：  无
*/
void displayList(NODE* head)
{
    NODE* p;
    for(p = head->pNext; p != head; p = p->pNext)
    {
        printf("%d ",p->num);
    }
    printf("\n");
}

/*
* 函数功能：   在原链表首节点之前插入一个新节点
* int n：      新节点的数据
* NODE** head：原链表首节点的地址
* 返回类型：  无
*/
void insert_head1(int n, NODE** head)
{
    // 创建新节点
    NODE* pNew = createNode(n);
    if (pNew == NULL)
    {
        return;
    }

    // 新节点指向原链表的首节点
    pNew->pNext = *head;

    // 将新节点的起始地址赋值给*head
    // 也就是让原链表的首地址指向新节点
    *head = pNew;
}

/*
* 函数功能：   在原链表首节点之前插入一个新节点
* int n：      新节点的数据
* NODE* head： 原链表首节点的地址
* 返回类型：   返回新链表的首节点
*/
NODE* insert_head2(int n, NODE* head)
{
    // 创建新节点
    NODE* pNew = createNode(n);
    if (pNew == NULL)
    {
        return head;
    }

    // 新节点指向原链表的首节点
    pNew->pNext = head->pNext;
    head->pNext = pNew;

    return head;
}

/*
* 函数功能：   获取链表尾节点的指针
* NODE* head： 链表首节点的地址
* 返回类型：   返回尾节点指针
*/
NODE* getTailNode(NODE* head)
{
    if (head == NULL)
    {
        return NULL;
    }

    while(head->pNext != head)
    {
        head = head->pNext;
    }

    return head;
}

/*
* 函数功能：   在原链表尾节点之后插入一个新节点
* int n：      新节点的数据
* NODE* head： 原链表首节点的地址
* 返回类型：   返回新链表的首节点
*/
NODE* insert_tail(int n, NODE* head)
{
    // 创建新节点
    NODE* pNew = createNode(n);
    if (pNew == NULL)
    {
        return head;
    }

    // 获取原链表尾节点的指针
    NODE* pTail = getTailNode(head);
    if (pTail == NULL)
    {
        return pNew;
    }

    // 将原链表尾节点和新节点连接
    pNew->pNext = head;
    pTail->pNext = pNew;

    
    return head;
}

/*
* 函数功能：  计算节点数量
* NODE* head：链表首地址
* 返回类型：  节点个数
*/
int calcNodeCount(NODE* head)
{
    int count = 0;
    NODE* p = head;
    while (p != NULL)
    {
        count++;
        p = p->pNext;
    }

    return count;
}

/*
* 函数功能：   在原链表的pos位置插入一个新节点
* int n：      新节点的数据
* NODE* head： 原链表首节点的地址
* int pos：    插入的位置(0认为是首节点之前插入)
* 返回类型：   返回新链表的首节点
*/
NODE* insertNode(int n, NODE* head, int pos)
{
    // 判断插入位置是否有效
    int count = calcNodeCount(head);
    if (pos < 0 || pos > count)
    {
        printf("insert pos error!\n");
        return head;
    }

    // 插入位置为首节点之前
    if (pos == 0)
    {
        return insert_head2(n, head);
    }

    /*************插入的新节点非首节点***********/
    
    // 创建新节点
    NODE* pNew = createNode(n);
    if (pNew == NULL)
    {
        return head;
    }

    NODE* p = head;

    // 查找插入位置之前的节点指针
    int i = 0;
    for (i = 0; i < pos - 1; i++)
    {
        p = p->pNext;
    }

    // 将新节点和后向节点连接
    pNew->pNext = p->pNext;

    // 将新节点和前向节点连接
    p->pNext = pNew;

    return head;
}

/*
* 函数功能：        删除指定位置的节点
* NODE* head：     
* int pos：         删除的位置(0认为是首节点)
* 返回类型：        返回新链表的首节点
*/
NODE* deleteNode(NODE* head, int pos)
{
    // 判断插入位置是否有效
    int count = calcNodeCount(head);
    if (pos < 0 || pos >= count)
    {
        printf("delete pos error!\n");
        return head;
    }
    
    if (head == NULL)
    {
        return NULL;
    }

    // 删除首节点
    if (pos == 0)
    {
        // 1、记录待删除的首节点
        NODE* p = head;

        // 2、让首节点后移
        head = head->pNext;

        // 3、删除首节点
        free(p);
        p = NULL;

        // 4、返回新链表的首地址
        return head;
    }

    /*********************删除其他节点******************************/
    NODE* p = head;

    // 查找待删除节点之前的节点指针
    int i = 0;
    for (i = 0; i < pos - 1; i++)
    {
        p = p->pNext;
    }

    //if (p->pNext == NULL)
    //{
    //    return head;
    //}

    // 保存待删除节点的指针
    NODE* temp = p->pNext;

    // 将待删除节点前后两个节点连接起来
    p->pNext = temp->pNext;

    // 删除节点
    free(temp);
    temp = NULL;

    // 返回链表首节点
    return head;
}

/*
* 函数功能：       修改指定位置的节点数据
* NODE* head：     链表首节点的地址
* int pos：        修改的位置(0认为是首节点)
* int newData：    新的数据
* 返回类型：       无
*/
void modifyNode(NODE* head, int pos, int newData)
{
    if (pos < 0)
    {
        printf("modify pos error!\n");
        return;
    }

    NODE* p = head;

    int i = 0;
    for (i = 0; p != NULL && i < pos; i++)
    {
        p = p->pNext;
    }
    
    if (p != NULL)
    {
        p->num = newData;
    }
}

/*
* 函数功能：       对链表进行排序（冒泡排序）
* NODE* head：     链表首节点的地址
* 返回类型：       无
*/
void sortList(NODE* head)
{
    if (head == NULL || head->pNext == NULL)
    {
        return;
    }

    int num = calcNodeCount(head);

    int temp;

    int i, j;
    for (i = 0; i < num - 1; i++)
    {
        NODE* p = head;
        for (j = 0; j < num - i - 1; j++)
        {
            if (p->num  >  p->pNext->num)
            {
                temp = p->num;
                p->num = p->pNext->num;
                p->pNext->num = temp;
            }

            p = p->pNext;
        }
    }
}

int main()
{
    // 用于记录当前链表中首节点的地址
    NODE* pHead = initList();

    // 将节点插入链表中：头插法
    // insert_head1(5, &pHead);
    // insert_head1(4, &pHead);
    // insert_head1(3, &pHead);
    // insert_head1(2, &pHead);
    // insert_head1(1, &pHead);

    pHead = insert_head2(-5, pHead);
    pHead = insert_head2(-4, pHead);
    pHead = insert_head2(-3, pHead);
    pHead = insert_head2(-2, pHead);
    pHead = insert_head2(-1, pHead);

    // 将节点插入链表中：尾插法
     pHead = insert_tail(1, pHead);
    // pHead = insert_tail(2, pHead);
    // pHead = insert_tail(3, pHead);
    // pHead = insert_tail(4, pHead);


    // 将节点插入链表中：任意位置插入
    // 假设位置 0 代表头插
    // pHead = insertNode(111, pHead, 0);   // 前面14个元素
    // pHead = insertNode(222, pHead, 15);  // 15
    // pHead = insertNode(333, pHead, 15);  // 16
    // pHead = insertNode(444, pHead, 1);   // 17
    // pHead = insertNode(555, pHead, 13);  // 18
    // pHead = insertNode(666, pHead, 7);   // 19

    
    //// 按位置删除节点
    //pHead = deleteNode(pHead, 0);

    // 修改节点数据
    //modifyNode(pHead, -1, 1111);

    //sortList(pHead);

    // 打印链表所有元素
    displayList(pHead);

    // 销毁整个链表
    distroyList(pHead);

    return 0;
}
